package 图.有向图;

import 抽象数据类型.Digraph;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-03
 */
public class 查找有向环 {
    static class DirectedCycle {
        private boolean[] marked;
        private int[] edgeTo;
        private Stack<Integer> cycle;//有向环的所有顶点
        private boolean[] onStack; //递归条用栈上的所有顶点
        public DirectedCycle(Digraph g){
            onStack = new boolean[g.V()];
            edgeTo = new int[g.V()];
            marked = new boolean[g.V()];
            for (int i = 0; i < g.V(); i++) {
                if (!marked[i]) {
                    dfs(g,i);
                }
            }
        }

        private void dfs(Digraph g, int v) {
            onStack[v] = true;
            marked[v] = true;
            for (Integer w : g.adj(v)) {
                if (this.hasCycle()) {
                    return;
                } else if (!marked[w]) {
                    edgeTo[w] = v;
                    dfs(g, w);
                } else if (onStack[w]) {
                    cycle = new Stack<>();
                    for (int x = w; x != w; x = edgeTo[x]) {
                        cycle.push(x);
                    }
                    cycle.push(w);
                    cycle.push(v);
                }
            }
            onStack[v] = false;
        }

        public boolean hasCycle() {
            return cycle != null;
        }

        public Iterable<Integer> cycle() {
            return cycle;
        }
    }

}
